离散数学第一章：集合及其运算

2023-03-26 04:33| 来源: 网络整理| 查看: 265

集合及其运算 集合的基本概念 集合和元素 定义：把一些确定的、彼此不同的事物作为一个整体来看待时，这个整体便称为是一个集合．组成集合的那些个体称为集合的元素．特征确定性互异性不重复性无序性抽象性

特殊集合：一个包含了研究问题中涉及的所有对象的集合，称为该问题的全域集合，简称全集，记作 U 或 E．不含任何元素的集合称为空集，记为Φ ．

集合的表示方法 列举法描述法递归定义法维恩图法集合的基数 定义：集合 A 所含不同元素的个数称为 A 的基数或势，记作#A 或|A|．若#A 是有限数，则称集合 A 为有限集，否则称 A 为无限集．空集Φ 为有限集且基数为零，任何非空集合的基数大于零．集合间的关系 集合的包含 定义设有集合 A，B，如果 A 的每一个元素都是 B 的元素，即对任意的x ∈ A都有x ∈ B，则称A是B的子集或B是A的包含集，记作A ⊆ B或B ⊇ A .如果 A 不是 B 的子集，即 A 中至少有一个元素不属于 B，则记作 A ⊈ B 或 B ⊉ A .若 A ⊆ B，且 B 中至少有一个元素不属于 A，则称 A 是 B 的真子集称 ⊆（或 ⊇ ）为包含关系，称 ⊂（或 ⊃ ）为真包含关系．

性质对任意的集合 A，有 Φ ⊆ Α对任意的集合 A，有 A ⊆ Α 对任意的集合 A，B，C，若 A ⊆ B，B ⊆ C，则 A ⊆ C

集合的相等 设有集合 A，B，若 A ⊆ B 且 B ⊆ A，则称集合 A 与 B 相等，记作 A = B．否则称集合 A 与 B 不相等，记作 A ≠ B．空集是唯一的 .（由相等关系证明）维恩图幂集由集合A的所有子集组成的集合，称为A的幂集，记作 2^A或P(A)，即 2^A = {S | S ⊆ A}．常称所有元素都是集合的集合为集合族．设 A 是有限集，则#(2^A) = 2^#A． 有限集合幂集元素的编码表示集合的运算和运算定律 集合的运算 并交补环合由属于 A 而不属于 B 以及属于 B 而不属于 A 的所有元素组成的集合环积（环合的补）

对于全集 U 的任意子集 A，B，C，有（1）A ⊆ A ∪ B，B ⊆ A ∪ B．（2）A ∩ B ⊆ A，A ∩ B ⊆ B．（3）A – B ⊆ A．（4）A – A = Φ ，A – Φ = A，A – U = Φ ．（5）A – B = A ∩ B′，A – B = A – A ∩ B．（6）(A′)′ = A，U′ = Φ ， Φ ′ = U．（7）若 A ⊆ C，B ⊆ C，则 A ∪ B ⊆ C．（8）若 A ⊆ B，A ⊆ C，则 A ⊆ B ∩ C．（9）若 A ⊆ B，则 B′ ⊆ A′．（10）A ⊆ B，A ∪ B = B，A ∩ B = A，A – B = Φ 之间相互等价．

集合运算的定律 对于全集 U 的任意子集 A，B，C，有（1）交换律：A ∪ B = B ∪ A，A ∩ B = B ∩ A．（2）结合律：A ∪ (B ∪ C) = (A ∪ B) ∪ C， A ∩ (B ∩ C) = (A ∩ B) ∩ C．（3）分配律：A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)， A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)．（4）同一律：A ∪ Φ = A，A ∩ U = A．（5）互补律：A ∪ A′ = U（又称为排中律），A ∩ A′ = Φ （又称为矛盾律）．（6）对合律：(A′)′ = A（又称为双重否定律）．（7）幂等律：A ∪ A = A，A ∩ A = A．（8）零一律：A ∪ U = U，A ∩ Φ = Φ ．（9）吸收律：A ∪ (A ∩ B) = A，A ∩ (A ∪ B) = A．（10）德·摩根律：(A ∪ B)′ = A′ ∩ B′，(A ∩ B)′ = A′ ∪ B′．

对于全集 U 的任意子集 A，B，C，有（1）交换律：A ⊕ B = B ⊕ A，A ⊗ B = B ⊗ A．（2）结合律：(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)，(A ⊗ B) ⊗ C = A ⊗ (B ⊗ C)．（3）同一律：A ⊕ Φ = A，A ⊕ U = A′， A ⊗ U = A，A ⊗ Φ = A′．（4）零一律：A ⊕ A = Φ ，A ⊕ A′ = U， A ⊗ A = U，A ⊗ A′ = Φ ．（5）其它律：A ⊕ B = A′ ⊕ B′，A ⊗ B = A′ ⊗ B′， A′ ⊕ B = A ⊕ B′ = A ⊗ B．

集合恒等式的证明方法 定义：要证明集合 A = B，根据定义，我们需证明 A ⊆ B 且 B ⊆ A．利用已有的集合恒等式证明利用集合成员表证明 包含排斥原理 由集合运算的定义知（1）若 A，B 不相交，则#(A ∪ B) = #A + #B．（2）max(#A，#B) ≤ #(A ∪ B) ≤ #A + #B．（3）#(A ∩ B) ≤ min(#A，#B)．（4）#A – #B ≤ #(A – B) ≤ #A．（5）若 A ⊆ B，则#A ≤ #B；#(B – A) = #B – #A．（6）#A′ = #U – #A．

设 A，B 为有限集合 U 的任意子集，则 #(A ∪ B) = #A + #B – #(A ∩ B) 推论 1 设 A， B 为有限集合 U 的任意子集，则 #(A ⊕ B) = #A + #B – 2#(A ∩ B)．推论 2 可拓展至n个子集

集合成员表集合的覆盖与分划 定义设 A 是一个非空集合，H = {A1，A2，…，Am}，其中 Ai ⊆ A，且 Ai ≠ Φ （i = 1，2，…，m）（1）若 A1∪A2...∪Am = A，则称 H 是 A 的一个覆盖．（2）若还有，当 i ≠ j 时 Ai ∩ Aj = Φ ，则称覆覆盖盖 H 是集合 A 的一个分划，每一个 Ai（i = 1，2，…，m）称为该分划的一个分划块．

设 S = {A1，A2，…，Am}和 T = {B1，B2，…，Bn}都是非空集合 A 的分划如果 T 中的每个分划块都含于 S 的某个分划块中，即∀Bi ∈ T，都存在 Aj ∈ S，使得 Bi ⊆ Aj，则称分划 T 是分划 S 的一个细分．如果 T 是 S 的一个细分，且 T 中至少有一个分划块为 S 中某个分划块的真子集，则称 T 是 S 的真细分．显然，每个分划都是其自身的一个细分，但不是真细分．

集合的标准形式 最小集标准形式 设 A1，A2，…，Ar是全集 U 的子集，形如S1 ∩S2 ∩... ∩Sr的集合称为由 A1，A2，…，Ar所产生的最小集，其中每个 Si为 Ai或 Ai′．最小集是包含所有 r 个子集（Ai或 Ai′，i = 1，2，…，r）的交集．由 A1，A2，…，Ar所产生的最小集共有 2^r个．最小集可能为空集．任意两个不同的最小集不相交．

由 A1，A2，…，Ar所产生的所有非空最小集的集合构成 U 的一个分划．由 A1，A2，…，Ar产生的集合 S 或为空集或为由 A1，A2，…，Ar产生的不同最小集的并集．当一个集合被表示为不同最小集的并集的形式时，此形式称为该集合的最小集标准形式或最小集范式．最大集标准形式 设 A1，A2，…，Ar是全集 U 的子集，形如S1US2...Sr 的集合称为由 A1，A2，…，Ar所产生的最大集，其中每个 Si为 Ai或 Ai′．最大集是包含所有 r 个子集（Ai或 Ai′，i = 1，2，…，r）的并集．由 A1，A2，…，Ar所产生的最大集共有 2^r个．最大集可能为全集．由 A1，A2，…，Ar所产生的最大集的集合不构成 U 的分划．因为两个不同的最大集可能相交．

当一个集合被表示为不同最大集的交的形式时，此形式称为该集合的最大集标准形式或最大集范式 .集合范式的说明设 S 是由 A1，A2，…，Ar产生的集合，若不计最小集（最大集）的排列次序，则 S 的最小集（最大集）范式是唯一的．由 A1，A2，…，Ar产生的两个集合相等的充分必要条件是它们最小集（或最大集）范式相同．

写在最后：其实总结这个专栏也不是给别人看的，现在疫情在家学习没有动力，就用Xmind做知识导图来鞭策自己，我没有订阅，所以公式没法打，也懒得在markdown下再编辑了，就直接导出来了上传。

后续还会上传其他章节的，已经决定除了离散还会做线代的。

【本文地址】

公司简介

联系我们